package com.dylan.历史.算法;

/**
 * @Auther: ankang
 * @Date: 2019/1/29 11:47
 * @Description:
 */
public class 背包0_1_动态规划 {

    /**
     * 对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，
     * 背包中物品重量的最大值是多少？
     */
    public static void main(String[] args) {
        int maxW = knapsack1(new int[]{1, 1, 5, 5, 5, 10, 10}, 34);
        System.out.println(maxW);
        maxW = knapsack2(new int[]{1, 1, 5, 5, 5, 10, 10}, 34);
        System.out.println(maxW);
    }

    /**
     * 用二维数组记录分层决策动态规划结果
     * @param items 物品重量
     * @param w 背包可承受的重量
     * @return 最大重量
     */
    private static int knapsack1(int[] items, int w) {
        int n = items.length; // 物品数量
        boolean[][] states = new boolean[n][w + 1]; // 默认值为false
        states[0][0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
        states[0][items[0]] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= w; j++) { // 不把第i个物品放入背包
                if (states[i - 1][j] == true) {
                    states[i][j] = states[i - 1][j];
                }
            }
            for (int j = 0; j <= w; j++) { // 把第i个物品放入背包
                if (states[i - 1][j] == true && j + items[i] <= w) {
                    states[i][j + items[i]] = true;
                }
            }
        }
        for (int i = w; i >= 0; i--) {
            if (states[n - 1][i] == true) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 用一维数组记录分层决策动态规划结果
     * @param items 物品重量
     * @param w 背包可承受的重量
     * @return 最大重量
     */
    private static int knapsack2(int[] items, int w) {
        int n = items.length; // 物品数量
        boolean[] states = new boolean[w + 1];
        states[0] = true; // 第一个物品要特殊处理，放入背包与不放入背包
        states[items[0]] = true;
        for (int i = 1; i < n; i++) { // 考察每一个物品
            for (int j = w - items[i]; j >= 0; j--) { // 把第i个物品放入背包
                if (states[j] == true) {
                    states[j + items[i]] = true;
                }
            }
        }
        for (int i = w; i >= 0; i--) {
            if (states[i] == true) {
                return i;
            }
        }
        return 0;
    }
}
